package airthmetic.exercise.arr;

import java.util.Arrays;

public class _56_合并区间 {
    public int[][] merge(int[][] intervals) {
        // 根据左边界排序
        Arrays.sort(intervals, (v1, v2)->{return v1[0] - v2[0];});
        int n = intervals.length;
        int idx = -1;
        int[][] res = new int[n][2];
        for(int[] interval : intervals){
            // 第一个元素直接进入最终返回
            // 非第一个元素 与最终返回的元素比较 (有一个指针)
            if(idx == -1 || interval[0] > res[idx][1]){
                // 如果 当前循环元素的左边界大于指针指向元素的右边界,当前元素加入最终返回数组
                res[++idx] = interval;
            }else{
                // 反之将当前区间合并至结果数组的最后区间
                res[idx][1] = Math.max(interval[1], res[idx][1]);
            }
        }

        return Arrays.copyOf(res, idx + 1);
    }

    public static void main(String[] args) {
        _56_合并区间 v = new _56_合并区间();
        int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};

        int[][] merge = v.merge(intervals);

        for (int[] ints : merge) {
            for (int anInt : ints) {
                System.out.println(anInt);

            }
            System.out.println("=================================================================");
        }
    }
}
